package main

import (
	"fmt"
	"math/rand"
	"sort"
)

func main() {
	//1、看下面一段程序，回答问题
	//s1 := make([]int, 3, 4)
	//s2 := append(s1, 1)
	//请问s1、s2内各有什么元素？
	//s1 创建了类型为[]int的切片，他的len为3，cap为4，这个数组切片可以表示为[0 0 0]
	//s2 在s1的基础上追加了一个1，他的len为4，cap为4，s1与s2指向同一个底层数组，但是引用不同的部分，
	//s1\s2 header结构体中指向数组指针的地址相同
	//s1修改一个元素会影响s2吗？s2修改一个元素会影响s1吗
	//有可能会影响，因为他们共用一个底层数组，如果s2修改的元素不在s1所引用底层数组的范围内，则不会影响。
	//s2在增加一个元素会怎么样？
	//s2当前len=4,cap=4,如果再增加元素则会在内存中另开辟一段空间，根据扩容原则计算，newlen=5 < 2oldcap < 256
	//newcap=8,s2将指向底层数组的指针指向新开辟的数组，将之前的数据复制进去并且追加新数据,s1不变
	//2、有一个数组[1,4,9,16,2,5,10,15],生成一个新切片，要求新切片元素是数组相邻2项的和。
	var a = [8]int{1, 4, 9, 16, 2, 5, 10, 15}
	var b = make([]int, 0, 4)
	var x int
	for i, v := range a {
		if i%2 == 0 {
			x = v + a[i+1]
			b = append(b, x)
		}
	}
	fmt.Printf("旧的数组为a的类型为%[2]T,值为%[2]d\n新切片b的类型是%[1]T,值为%[1]d\n", b, a)
	//3、数字重复统计
	//随机产生100个整数
	//数字的范围[-100, 100]
	//降序输出这些生成的数字并打印其重复的次数
	var (
		rd  int
		prd int
		ird int
	)
	rds := make([]int, 0, 200)
	crds := make([]int, 100)
	for i := 0; i < 100; i++ {
		rd = rand.Intn(101)
		rds = append(rds, rd)
	}
	for i := 0; i < 100; i++ {
		prd = -rand.Intn(101)
		rds = append(rds, prd)
	}
	for i := range crds {
		ird = rand.Intn(200)
		crds[i] = rds[ird]
	}
	sort.Sort(sort.Reverse(sort.IntSlice(crds)))
	crdmap := make(map[int]int, 100)
	for _, v := range crds {
		if crdmap[v] != 0 {
			crdmap[v]++
		} else {
			crdmap[v] = 1
		}
	}

	for i, v := range crds {
		if i == 0 {
			if v != crds[i+1] {
				fmt.Printf("%d:%d次\n", v, crdmap[v])
			} else {
				fmt.Printf("%d:%d次\n", v, crdmap[v])
			}
		} else if i == 99 {
			if v != crds[i-1] {
				fmt.Printf("%d:%d次\n", v, crdmap[v])
			}
		} else if v == crds[i+1] && v != crds[i-1] {
			fmt.Printf("%d:%d次\n", v, crdmap[v])
		} else if v != crds[i+1] && v != crds[i-1] {
			fmt.Printf("%d:%d次\n", v, crdmap[v])
		}
	}
	//4、简述线性数据结构和哈希表优劣
	//	线性数据结构特点：
	//	1)逻辑上它是一组数据，可以包含任意个，其中元素必须确定先后顺序，有头有尾，可索引
	//	2)它的物理实现有顺序表和链接表
	//		a.顺序表的实现在内存中占有一段连续的内存空间，每个元素在其中占用相同的字节数，表中元素有头有尾
	//			顺序表增加元素时长度加1，如果增加元素在首部，则全部原全部元素需要后移(每个元素都要向后copy)
	//			，第一个元素放入新元素;如果在中间插入元素，插入点之后的元素需要后移（copy）;如果在结尾添加
	//			直接放到最后就可以。如果上述三种添加方式没有足够空间，需要在内存中另外开辟，将原有元素全部copy
	//			过来。
	//			顺序表删除元素时长度减1，首部删除，所有元素向前移动(copy)；中间删除，从删除元素开始向前移动(copy)
	//			;尾部删除，"静悄悄"删除。
	//			顺序表修改元素，首先需要定位，头部已有指针记录地址，通过首地址加offset(index*每个元素占用
	//			的字节数)可以快速定位O(2)；如果不是根据索引查找，则需要逐个元素遍历比较，速度较慢,查找难度
	//			随数据规模增加O(n)，也要看运气，如果查找位置就在首部则一次命中。找到后更新内容
	//		b.链接表的在内存构建可以分散存放，每个元素包含next、prev指针，除此之外还有存储长度、head、tail
	//		的元数据
	//			链接表增加元素时长度加1，如果增加在首部，则原首部元素prev指向新头，新头next指向原头，prev悬空，
	//			head指向新头;如果增加在中部，则插入点前元素next改指向新元素，新元素prev指向前一个元素，next指向
	//			插入点之后的元素，插入点之后的元素prev指向新元素;如果插入点在尾部，则旧尾部指向新尾部，新尾部prev
	//			指向旧尾部，新尾部next悬空，元数据tail修改为新尾部。
	//			链接表三处元素时与增加类似，也是主要对next、prev、tail、head、len进行修改，一般不会造成顺序表
	//			那种大量copy的情况。
	//			修改元素首先需要定位查找，可根据指针进行查找，如果所修改元素在头尾，则根据元数据一次命中修改，
	//			如果在中段，则需要根据每个元素的next查找逐个匹配，相对于顺序表效率较低，查找难度随规模增加O(n)
	//			如果不是根据索引查找，则需要逐一遍历，查找难度O(n),修改元素只需更新内容，不需要修改prev、next
	//	哈希表优势
	//		特点：无序，不可索引，基于key查找value，时间复杂度是O(1),key唯一，value不做要求，长度可变，存在桶数组用来存放k,v对，
	//		基于hash(key)%(2^B)查找和放入元素
	//		增：count(长度)加1，通过hash(key)%(2^B)可放入的桶索引后放入元素，如果存在则覆盖
	//		删：基于hash(key)%(2^B)查找对应的桶并删除元素，count-1
	//		改：基于hash(key)%(2^B)查找对应的桶并找到桶中对应key的value进行修改
	//		查：基于hash(key)%(2^B)查找对应的桶并找到key对应的元素
	//		扩容：LoadFactor>6.5时，B++，即扩容桶数组为原来的两倍，LoadFactor=count/2^B
	//			扩容策略
	//				增量扩容LoadFactor>6.5时，B++，即扩容桶数组为原来的两倍，LoadFactor=count/2^B
	//				每次扩容会有一半的老桶数据重新计算对应索引后会迁移至新桶
	//				go语言实现，新数据会写入新桶，老数据会重新计算对应桶索引，将采用渐进式迁移，将至多两个老桶数据进行迁移
	//			等量扩容
	//				go语言每个桶中的拉链法做过特殊处理，桶中链表中每个节点都会指向一个顺序表，长度为8，当达到一定阈值后触发等量扩容
	//				即将因删除操作而分散存储在各个数组中元素整合到一起，将多余空间清除出来，即桶数组长度不变，完成扩容，是一种回收利用的策略
}
